package day005;

public class Code03_KMP {


    public static int indexOf(String s, String m) {
        if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
            return -1;
        }
        char[] str1 = s.toCharArray();
        char[] str2 = m.toCharArray();
        int i1 = 0;
        int i2 = 0;
        int[] next = getNextArray(str2);
        while (i1 < str1.length && i2 < str2.length) {
            if (str1[i1] == str2[i2]) {
                i1++;
                i2++;
            } else if (i2 == 0) {  // i2已经到头了，没法左移了，只能换i1下个字符匹配了
                i1++;
            } else {
                i2 = next[i2];
            }
        }
        // i1 == str1.length 或者 i2 == str2.length
        // 只有匹配相等i2才会++，其余条件都是不动或者往前，所以i2 == st2.length表明已经匹配成功
        return i2 == str2.length ? i1 - i2 : -1;
    }

    private static int[] getNextArray(char[] str2) {
        if (str2.length == 1) {
            return new int[]{-1};
        }
        int[] next = new int[str2.length];
        // 人为规定
        next[0] = -1;
        next[1] = 0;
        int i = 2; // next需要计算的开始位置  next[2]
        int cn = 0;// cn 表示前一个数的信息，
        while (i < next.length){
            if(str2[i -1] == str2[cn]){
                // next[i++] = ++cn;
                cn++;   // 计算next[i+1] 开始的地方
                next[i] = cn;
                i++; // 下一个
            }else if(cn > 0){ // 当前跳到cn位置的字符和i-1位置上的字符配不上
                cn = next[cn];
            }else{
                next[i] = 0;
                i++; // 下一个
            }
        }
        return next;
    }

    public static void main(String[] args) {
        String str1 = "abbstkscabbstkscabbstkz";
        String str2 = "abbstkscabbstkz";
        int res = indexOf(str1, str2);
        System.out.println(res);

    }
}
